package org.aplombh.java.awcing.basic.graph.shortestPath.bellmanFord;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
 * <p>
 * 请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
 * <p>
 * 注意：图中可能 存在负权回路 。
 * <p>
 * 输入格式
 * 第一行包含三个整数 n,m,k。
 * <p>
 * 接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 * <p>
 * 输出格式
 * 输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
 * <p>
 * 如果不存在满足条件的路径，则输出 impossible。
 * <p>
 * 数据范围
 * 1≤n,k≤500,
 * 1≤m≤10000,
 * 任意边长的绝对值不超过 10000。
 * <p>
 * 输入样例：
 * 3 3 1
 * 1 2 1
 * 2 3 1
 * 1 3 3
 * 输出样例：
 * 3
 */
public class ShortPathOfEdgeLimit_853 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        Edge[] edges = new Edge[ShortPath.N];
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int w = scanner.nextInt();
            edges[i] = new Edge(a, b, w);
        }
        ShortPath shortPath = new ShortPath(edges);
        int path = shortPath.bellmanFord(n, m, k);
        if (path == -1) System.out.println("impossible");
        else System.out.println(path);
    }
}

class ShortPath {
    public static final int N = 100010;
    Edge[] edges = new Edge[N];
    int[] dist, backup;

    ShortPath(Edge[] edges) {
        init(edges);
    }

    void init(Edge[] edges) {
        dist = new int[N];
        this.edges = edges.clone();

        Arrays.fill(dist, 1 << 30);
        dist[1] = 0;

    }

    int bellmanFord(int n, int m, int k) {
        for (int i = 0; i < k; i++) {
            // 备份，防止本次更新更改路径而导致的路径问题 Backup to prevent path problems caused by path changes during this update
            backup = dist.clone();
            for (int j = 0; j < m; j++) {
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if (dist[n] > 1 << 30 / 2) return -1;
        return dist[n];
    }
}

class Edge {
    int a, b, w;

    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}